package com.shangguigu.binarytree;

/**
 * @author: ZhouBert
 * @date: 2019/10/25
 * @description: 顺序存储二叉树 数组转二叉树（完全二叉树）
 */
public class ArrBinaryTree {

	private int[] arr;

	public ArrBinaryTree(int[] arr) {
		this.arr = arr;
	}

	/**
	 * 前序遍历
	 */
	public void preOrder(){
		preOrder(0);
	}

	/**
	 * 中序遍历
	 */
	public void inOrder(){
		if (arr==null||arr.length==0){
			return;
		}
		inOrder(0);
	}


	/**
	 * 根据规律实现前序遍历
	 * @param index
	 */
	private void preOrder(int index){
		if (arr==null||arr.length==0){
			return;
		}
		//根据公式：第n个元素的左子节点为2*n+1
		System.out.println(arr[index]);
		//遍历左节点
		if (2*index+1<arr.length){
			preOrder(2*index+1);
		}
		if(2*index+2<arr.length){
			preOrder(2*index+2);
		}
	}

	/**
	 * 中序遍历二叉树
	 * @param index
	 */
	private void inOrder(int index){
		///遍历左边
		int leftIndex=2*index+1;
		if (leftIndex<arr.length){
			inOrder(leftIndex);
		}
		System.out.println(arr[index]);

		///遍历右边
		int rightIndex=2*index+2;
		if(rightIndex<arr.length){
			inOrder(rightIndex);
		}

	}

	public static void main(String[] args) {
		int[] arr = {1, 2, 3, 4, 5, 6, 7};
		//	   1
		//  2	  3
		//4  5	6	7
		ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
		arrBinaryTree.preOrder();
		arrBinaryTree.inOrder();
	}


}
